package nowcoder.written_examination.tencent;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @author fance
 * @date 18-7-2 上午10:21
 */
public class Main {
    public String[] getGray(int n) {
        // write code here
        if(n == 1){
            return new String[]{"0","1"};
        }else {
            String[] temp = getGray(n - 1);
            String[] result= new String[temp.length*2];
            for (int i = 0; i < temp.length; i++) {
                result[i] = "0" + temp[i];
            }
            int i,j;
            for (i = 0,j = temp.length - 1; i < temp.length && j >= 0;i++,j--) {
                result[i + temp.length] = "1" + temp[j];
            }
            return result;
        }
    }

    public int getValue(int[] gifts, int n) {
        // write code here
        // 1.sort not fit 2.cnt 3.投票法... todo
        if (gifts == null || n < 1) {
            return 0;
        }
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(gifts[i],map.getOrDefault(gifts[i],0) + 1);
        }
        for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
            if (entry.getValue() > n / 2) {
                return entry.getKey();
            }
        }
        return 0;
    }
    public int getValueII(int[] gifts, int n) {
        // write code here
        // 1.sort not fit 2.cnt 3.投票法... todo
        int majority = gifts[0];
        int cnt = 1;
        for (int i = 1; i < n; i++) {
            if (cnt == 0) {
                majority = gifts[i];
                cnt++;
                continue;
            }
            if (gifts[i] == majority) {
                cnt++;
            } else {
                cnt--;
            }

        }
        cnt = 0;
        for (int i = 0; i < n; i++) {
            if (gifts[i] == majority) {
                cnt++;
            }
        }
        return cnt <= n / 2 ? 0 : majority;
    }

    public int getValueAgain(int[] gifts, int n) {
        // write code here
        int majority = gifts[0];
        int cnt = 1;
        for (int i = 1; i < n; i++) {
            if (cnt == 0) {
                majority = gifts[i];
                cnt = 1;
                continue;
            }
            if (gifts[i] == majority) {
                cnt++;
            } else {
                cnt--;
            }
        }
        cnt = 0;
        for (int i = 0; i < n; i++) {
            if (gifts[i] == majority) {
                cnt++;
            }
        }
        return cnt <= n / 2 ? 0 : majority;
    }
    @Test
    public void test() {
        String[] res = getGray(2);
        for (String s : res) {
            System.out.print(s);
        }
    }
}
